package com.atguigu.avl;



public class AVLTreeDemo {

	public static void main(String[] args) {
		//int[] arr = {4,3,6,5,7,8};
		//int[] arr = { 10, 12, 8, 9, 7, 6 };
		int[] arr = { 10, 11, 7, 6, 8, 9 };  
		//??????? AVLTree????
		AVLTree avlTree = new AVLTree();
		//?????
		for(int i=0; i < arr.length; i++) {
			avlTree.add(new Node(arr[i]));
		}
		
		//????
		System.out.println("???????");
		avlTree.infixOrder();
		
		System.out.println("???????~~");
		System.out.println("??????=" + avlTree.getRoot().height()); //3
		System.out.println("?????????????=" + avlTree.getRoot().leftHeight()); // 2
		System.out.println("?????????????=" + avlTree.getRoot().rightHeight()); // 2
		System.out.println("?????????=" + avlTree.getRoot());//8
		
		
	}

}

// ????AVLTree
class AVLTree {
	private Node root;

	public Node getRoot() {
		return root;
	}

	// ????????????
	public Node search(int value) {
		if (root == null) {
			return null;
		} else {
			return root.search(value);
		}
	}

	// ????????
	public Node searchParent(int value) {
		if (root == null) {
			return null;
		} else {
			return root.searchParent(value);
		}
	}

	// ???????:
	// 1. ????? ??node ??????????????????????????
	// 2. ???node ????????????????????????
	/**
	 * 
	 * @param node
	 *            ???????(????????????????????)
	 * @return ????? ??node ??????????????????????????
	 */
	public int delRightTreeMin(Node node) {
		Node target = node;
		// ????????????????????????
		while (target.left != null) {
			target = target.left;
		}
		// ??? target?????????????
		// ?????????
		delNode(target.value);
		return target.value;
	}

	// ??????
	public void delNode(int value) {
		if (root == null) {
			return;
		} else {
			// 1.?????????????????? targetNode
			Node targetNode = search(value);
			// ?????????????????
			if (targetNode == null) {
				return;
			}
			// ?????????????????????????????????
			if (root.left == null && root.right == null) {
				root = null;
				return;
			}

			// ????targetNode??????
			Node parent = searchParent(value);
			// ??????????????????
			if (targetNode.left == null && targetNode.right == null) {
				// ???targetNode ???????????????????????
				if (parent.left != null && parent.left.value == value) { // ????????
					parent.left = null;
				} else if (parent.right != null && parent.right.value == value) {// ????????
					parent.right = null;
				}
			} else if (targetNode.left != null && targetNode.right != null) { // ?????????????????
				int minVal = delRightTreeMin(targetNode.right);
				targetNode.value = minVal;

			} else { // ?????????????????
				// ???????????????????
				if (targetNode.left != null) {
					if (parent != null) {
						// ??? targetNode ?? parent ????????
						if (parent.left.value == value) {
							parent.left = targetNode.left;
						} else { // targetNode ?? parent ????????
							parent.right = targetNode.left;
						}
					} else {
						root = targetNode.left;
					}
				} else { // ???????????????????
					if (parent != null) {
						// ??? targetNode ?? parent ????????
						if (parent.left.value == value) {
							parent.left = targetNode.right;
						} else { // ??? targetNode ?? parent ????????
							parent.right = targetNode.right;
						}
					} else {
						root = targetNode.right;
					}
				}

			}

		}
	}

	// ?????????
	public void add(Node node) {
		if (root == null) {
			root = node;// ???root??????????root???node
		} else {
			root.add(node);
		}
	}

	// ???????
	public void infixOrder() {
		if (root != null) {
			root.infixOrder();
		} else {
			System.out.println("?????????????????????");
		}
	}
}

// ????Node???
class Node {
	int value;
	Node left;
	Node right;

	public Node(int value) {

		this.value = value;
	}

	// ??????????????
	public int leftHeight() {
		if (left == null) {
			return 0;
		}
		return left.height();
	}

	// ??????????????
	public int rightHeight() {
		if (right == null) {
			return 0;
		}
		return right.height();
	}

	// ???? ??????????????????
	public int height() {
		return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
	}
	
	//?????????
	private void leftRotate() {
		
		//????????????????????
		Node newNode = new Node(value);
		//????????????????????????????????
		newNode.left = left;
		//???????????????????????????????????????????
		newNode.right = right.left;
		//?????????????????????
		value = right.value;
		//???????????????????????????????????????
		right = right.right;
		//??????????????(??????)???????????
		left = newNode;
		
		
	}
	
	//?????
	private void rightRotate() {
		Node newNode = new Node(value);
		newNode.right = right;
		newNode.left = left.right;
		value = left.value;
		left = left.left;
		right = newNode;
	}

	// ????????????
	/**
	 * 
	 * @param value
	 *            ????????????
	 * @return ??????????????????null
	 */
	public Node search(int value) {
		if (value == this.value) { // ??????????
			return this;
		} else if (value < this.value) {// ???????????????????????????????
			// ????????????
			if (this.left == null) {
				return null;
			}
			return this.left.search(value);
		} else { // ?????????????????????????????????
			if (this.right == null) {
				return null;
			}
			return this.right.search(value);
		}

	}

	// ????????????????
	/**
	 * 
	 * @param value
	 *            ??????????
	 * @return ??????????????????????????????null
	 */
	public Node searchParent(int value) {
		// ??????????????????????????????
		if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
			return this;
		} else {
			// ???????????????????, ???????????????????
			if (value < this.value && this.left != null) {
				return this.left.searchParent(value); // ??????????????
			} else if (value >= this.value && this.right != null) {
				return this.right.searchParent(value); // ??????????????
			} else {
				return null; // ???????????
			}
		}

	}

	@Override
	public String toString() {
		return "Node [value=" + value + "]";
	}

	// ?????????
	// ????????????????????????????????????
	public void add(Node node) {
		if (node == null) {
			return;
		}

		// ????????????????????????????????
		if (node.value < this.value) {
			// ????????????????null
			if (this.left == null) {
				this.left = node;
			} else {
				// ???????????????
				this.left.add(node);
			}
		} else { // ???????????? ????????
			if (this.right == null) {
				this.right = node;
			} else {
				// ???????????????
				this.right.add(node);
			}

		}
		
		//?????????????????: (??????????-??????????) > 1 , ?????
		if(rightHeight() - leftHeight() > 1) {
			//??????????????????????????????????????????????????
			if(right != null && right.leftHeight() > right.rightHeight()) {
				//?????????????????
				right.rightRotate();
				//???????????????????
				leftRotate(); //?????..
			} else {
				//???????????????
				leftRotate();
			}
			return ; //?????!!!
		}
		
		//????????????????? (?????????? - ??????????) > 1, ?????
		if(leftHeight() - rightHeight() > 1) {
			//?????????????????????????????????????????
			if(left != null && left.rightHeight() > left.leftHeight()) {
				//?????????????(??????)->?????
				left.leftRotate();
				//????????????????
				rightRotate();
			} else {
				//???????????????
				rightRotate();
			}
		}
	}

	// ???????
	public void infixOrder() {
		if (this.left != null) {
			this.left.infixOrder();
		}
		System.out.println(this);
		if (this.right != null) {
			this.right.infixOrder();
		}
	}

}
